home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / clean / sun3.lha / Sun3 / pardemos / sieve.icl < prev    next >
Text File  |  1992-08-07  |  2KB  |  63 lines
  1. MODULE sieve;
  2.  
  3. <<
  4. The parallel Sieve of Eratosthenes.
  5.  
  6. A pipeline of reducers (Sieve's) is created. The Sieve reducers get their
  7. input [2,3,4,...] from the Gen process. The primes held by each sieve are
  8. communicated to a collecting process (Primes). In a picture:
  9.  
  10.      Primes <--+---------+---------+---------+ - - -
  11.                |         |         |         |
  12.      Gen -> Sieve2 -> Sieve3 -> Sieve5 -> Sieve7 -> ...
  13.  
  14. The result of the program is a list of all primes smaller than Limit.
  15.  
  16. Strictness annotations were added because the strictness analyzer doesn't
  17. derive strictness information from parallel functions, because that could
  18. lead to unexpected and unwanted results.
  19.  
  20. Run the program with the show constructors option on.
  21. >>
  22.  
  23. IMPORT deltaI;
  24.  
  25.  
  26. MACRO
  27.  
  28.     Limit -> 150;   == All primes < Limit will be computed.
  29.     
  30.     
  31. RULE
  32.  
  33. <<  Primes returns the list of primes. The Gen process is started up and the
  34.     function responsible for the creation of the Sieves is called.
  35. >>
  36. ::  Primes                  ->  [INT];
  37.     Primes                  ->  Sieve ({P} Gen 2);
  38.  
  39. <<  Gen is responsible for the creation of the Gen reducer that sends a
  40.     stream of integers greater than n to the first Sieve.
  41. >>
  42. ::  Gen INT                 ->  [INT];
  43.     Gen Limit               ->  [];
  44.     Gen n                   ->  [n | {I} Gen !(++ n)];
  45.  
  46. <<  Sieve creates the pipeline of Sieve reducers. On each processor a Filter
  47.     process is running that filters out all incoming numbers divisible by
  48.     the prime of the sieve.
  49. >>
  50. ::  Sieve [INT]             ->  [INT];
  51.     Sieve []                ->  [];
  52.     Sieve [p | s]           ->  [p | {P} Sieve ({I} Filter s p)];
  53.  
  54. ::  Filter  [INT]   !INT    ->  [INT];
  55.     Filter  []      p       ->  [];
  56.     Filter  [f | r] p       ->  [f | {I} Filter r p] , IF > (% f p) 0
  57.                             ->  Filter r p;
  58.  
  59. ==  The Start rule: call Primes.
  60.  
  61. ::  Start                   ->  [INT];
  62.     Start                   ->  Primes;
  63.